package tp6;

import java.util.Collection;
import java.util.HashSet;
import java.util.Set;

public class LinearHashTable<K, V> implements SimpleMap<K, V> {
	private int p = 0;
	private int alpha;
	private Bucket<K, V>[][] buckets;
	private int size = 0;
	private int origSize;

	@SuppressWarnings("unchecked")
	public LinearHashTable(int origSize, int alpha) {
		if (origSize <= 0 || alpha <= 0) {
			throw new IllegalArgumentException();
		}
		this.origSize = origSize;
		buckets = new Bucket[p][origSize];
		this.alpha = alpha;
	}

	@SuppressWarnings("unchecked")
	public LinearHashTable(int origSize, int alpha, int p) {
		if (origSize <= 0 || alpha <= 0) {
			throw new IllegalArgumentException();
		}
		this.origSize = origSize;
		buckets = new Bucket[p][origSize];
		this.alpha = alpha;
		this.p = p;
	}

	@Override
	public V get(K key) {
		boolean foundPlace = false;
		int hash = key.hashCode();
		int i = 0;
		for (; i < p && !foundPlace; i++) {
			if (hash % (origSize * (i + 1)) < origSize) {
				foundPlace = true;
			}
		}
		if (buckets[i][hash % origSize] == null) {
			return null;
		}
		return buckets[i][hash % origSize].value;
	}

	@Override
	public Set<K> keySet() {
		Set<K> set = new HashSet<K>();
		for (Bucket<K, V>[] innerBuck : buckets) {
			for (Bucket<K, V> b : innerBuck) {
				set.add(b.key);
			}
		}
		return set;
	}

	@Override
	public void put(K key, V value) {
		int hash = key.hashCode();
		if ((((double) size + 1) / ((double) (origSize * (p + 1)))) >= alpha) {
			grow(hash % origSize);
		}
		boolean foundPlace = false;

		int i = 0;
		for (; i < p && !foundPlace; i++) {
			if (hash % (origSize * (i + 1)) < origSize) {
				foundPlace = true;
			}
		}
		if (buckets[i][hash % origSize] == null) {
			buckets[i][hash % origSize] = new Bucket<K, V>(key, value, null);
		} else {
			buckets[i][hash % origSize].add(key, value);
		}
		size++;
	}

	@SuppressWarnings("unchecked")
	private void grow(int place) {
		if (place > p) {
			throw new IllegalArgumentException();
		}
		int newP = p + 1;

		Bucket<K, V>[][] aux = new Bucket[newP][origSize];
		int minCap = Math.min(buckets.length, aux.length);

		for (int bigCounter = 0; bigCounter < buckets.length; bigCounter++) {
			int i;
			for (i = 0; i < place; i++) {
				Bucket<K, V> current = buckets[bigCounter][i];
				do {
					int hash = current.key.hashCode();
					boolean foundPlace = false;

					int j = 0;
					for (; j < newP && !foundPlace; j++) {
						if (hash % (origSize * (j + 1)) < origSize) {
							foundPlace = true;
						}
					}
					if (aux[j][hash % origSize] == null) {
						aux[j][hash % origSize] = new Bucket<K, V>(current.key,
								current.value, null);
					} else {
						aux[j][hash % origSize].add(current.key, current.value);
					}
				} while (current != null);
			}

			for (; i < minCap; i++) {
				aux[i] = buckets[i];
			}
		}
		buckets = aux;
	}

	@SuppressWarnings("unchecked")
	private void shrink(int place) {
		if (place > p) {
			throw new IllegalArgumentException();
		}
		int newP = p - 1;

		Bucket<K, V>[][] aux = new Bucket[newP][origSize];
		int minCap = Math.min(buckets.length, aux.length);

		for (int bigCounter = 0; bigCounter < buckets.length; bigCounter++) {
			int i;
			for (i = 0; i < place; i++) {
				Bucket<K, V> current = buckets[bigCounter][i];
				do {
					int hash = current.key.hashCode();
					boolean foundPlace = false;

					int j = 0;
					for (; j < newP && !foundPlace; j++) {
						if (hash % (origSize * (j + 1)) < origSize) {
							foundPlace = true;
						}
					}
					if (aux[j][hash % origSize] == null) {
						aux[j][hash % origSize] = new Bucket<K, V>(current.key,
								current.value, null);
					} else {
						aux[j][hash % origSize].add(current.key, current.value);
					}
				} while (current != null);
			}

			for (; i < minCap; i++) {
				aux[i] = buckets[i];
			}
		}
		buckets = aux;
	}

	@Override
	public void remove(K key) {
		int hash = key.hashCode();
		boolean foundPlace = false;

		int i = 0;
		for (; i < p && !foundPlace; i++) {
			if (hash % (origSize * (i + 1)) < origSize) {
				foundPlace = true;
			}
		}
		if (buckets[i][hash % origSize] == null) {
			return;
		} else {
			buckets[i][hash % origSize].remove(key);
		}

		if ((((double) size - 1) / ((double) (origSize * (p + 1)))) >= alpha) {
			shrink(hash % origSize);
		}
		size--;
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public Collection<V> values() {
		Set<V> set = new HashSet<V>();
		for (Bucket<K, V>[] innerBucket : buckets) {
			for (Bucket<K, V> b : innerBucket) {
				set.add(b.value);
			}
		}
		return set;
	}

	static class Bucket<S, T> {
		S key;
		T value;
		Bucket<S, T> next;

		Bucket(S key, T value, Bucket<S, T> next) {
			this.key = key;
			this.value = value;
			this.next = next;
		}

		void add(S key, T value) {
			Bucket<S, T> current = this;
			while (current.next != null) {
				current = current.next;
			}
			current.next = new Bucket<S, T>(key, value, null);
		}

		void remove(S key) {
			Bucket<S, T> current = this;
			while (current.next != null) {
				if (current.key.equals(key)) {

				}
				current = current.next;
			}
			current.next = null;
		}

	}

}
